ยินดีต้อนรับสู่บทเรียนที่ 3 ของ แนวคิดปัญญาประดิษฐ์ (มหาวิทยาลัยโพลีเทคนิค รหัสวิชา COMP5511). ในบทนี้ เราจะเปลี่ยนจากเส้นทางการค้นหาแบบตัวแทนเดียวไปยัง การค้นหาเชิงขัดแย้ง, ซึ่งตัวแทนทำงานในสภาพแวดล้อมที่มีการแข่งขันระหว่างตัวแทนหลายตัว เราจะแนะนำ ปัญหาการจำกัดความสมบูรณ์ (CSPs), ซึ่งเป็นแนวทางที่มุ่งเน้นการค้นหาสถานะที่สอดคล้องกับชุดเงื่อนไขเฉพาะ มากกว่าการค้นหาเส้นทาง

แนวคิดหลัก

• การค้นหาเชิงขัดแย้ง: มุ่งเน้นอัลกอริธึมเช่น มินิแม็กซ์ และ การตัดต้นไม้อะล์ฟา-เบต้า เพื่อตัดสินใจอย่างมีเหตุผลต่อผู้เล่นที่มีสติ
• การค้นหาต้นไม้มอนต์คาร์โล (MCTS): สำรวจการตัดสินใจแบบสุ่ม ซึ่งเป็นหัวใจสำคัญของระบบปัญญาประดิษฐ์ในเกมสมัยใหม่ เช่น อัลฟากู.
• การจำกัดความสมบูรณ์: จำลองปัญหาโดยใช้ตัวแปร พื้นที่ค่า และข้อจำกัด โดยแก้ปัญหาด้วย การกลับไปตรวจสอบย้อนหลัง และ การค้นหาแบบท้องถิ่น.

การวิเคราะห์ความซับซ้อน

ในสภาพแวดล้อมที่มีการแข่งขัน ความซับซ้อนของพื้นที่การค้นหา มักกำหนดโดยตัวประกอบการแยกสาขาของเกม $b$ และระดับความลึก $d$, นำไปสู่ต้นทุนการคำนวณ: $$O(b^d)$$ การเติบโตแบบเอ็กซ์โพเนนเชียลนี้ทำให้ต้องใช้กลยุทธ์การตัดต้นไม้ที่มีประสิทธิภาพ เช่น การตัดต้นไม้อัลฟ่า-เบต้า